package backMind

// 矩阵中的路径
// 设计一个函数，判断在一个矩阵中是否存在一条包含某字符串所有字符的路径
// 路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左右上下方向移动
// 矩阵中每一个格子不能重复走

func HasPath(a [][]byte, rows, cols int, str string) bool {
	if len(str) == 0 {
		return false
	}
	if len(a) == 0 {
		return false
	}
	if rows < 1 || cols < 1 {
		return false
	}
	visited := make(map[byte]bool)
	var pathLength = 0
	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if hasPathCore(a, rows, cols, row, col, pathLength, str, visited) {
				return true
			}
		}
	}
	return false
}

func hasPathCore(a [][]byte, rows, cols, row, col, pathLength int, str string, visited map[byte]bool) bool {
	if pathLength == len(str) {
		return true
	}
	var hasPath = false
	if row >= 0 && row < rows && col >= 0 && col < cols && a[row][col] == str[pathLength] && !visited[a[row][col]] {
		pathLength++
		visited[a[row][col]] = true
		hasPath = hasPathCore(a, rows, cols, row, col-1, pathLength, str, visited) ||
			hasPathCore(a, rows, cols, row-1, col, pathLength, str, visited) ||
			hasPathCore(a, rows, cols, row, col+1, pathLength, str, visited) ||
			hasPathCore(a, rows, cols, row+1, col, pathLength, str, visited)
		if !hasPath {
			pathLength--
			visited[a[row][col]] = false
		}
	}
	return hasPath
}
